Handlungsreisendenproblem

Handlungsreisendenproblem

 

[engl. traveling salesman problem], ein Problem der theoretischen Informatik, mit dem grundlegende Fragen der Berechenbarkeit angesprochen werden.

 

Das Handlungsreisendenproblem gehört zur Gruppe der Reihenfolgenprobleme (kombinatorische Optimierung). Es geht bei ihm darum, die kürzeste Reiseroute für einen Vertreter zu finden, der eine mit k bezeichnete Anzahl von Orten besuchen soll, wobei der Ausgangsort nicht mitgezählt wird. Obwohl die Aufgabe einfach erscheint, da das Finden eines kurzen Wegs zu den menschlichen Alltagserfahrungen gehört, sind Computer damit schnell überfordert. Es gibt nämlich kein allgemeines Berechnungsverfahren für dieses Problem, ein Computer muss daher alle denkbaren Lösungen ausprobieren. Die Anzahl der möglichen Rundreisewege hängt aber von der Fakultät der Anzahl aller Orte (ohne den Ausgangsort) ab. Das Ergebnis muss dann noch halbiert werden, da man jeden Weg einer Rundreise in zwei Richtungen gehen kann. Damit existieren bei nur sechs Orten bereits über sechzig mögliche Wege, bei 15 Orten schon über 43 Milliarden. Je mehr Orte man in das Problem aufnimmt, desto größer wird der Rechenaufwand. Genau genommen steigt der Zeitaufwand für die Berechnung exponentiell mit der Zahl der zu besuchenden Orte.

 

Aus diesem Grund arbeitet man bei Problemen wie diesem mit Näherungsverfahren, die unter Berücksichtigung bereits bekannter Ergebnisse nach einem kürzeren Weg suchen, anstatt blind alle Wege nacheinander auszuprobieren. Ein interessanter Ansatz, bei dem der Algorithmus in Erbsubstanz-(DNA-)Abschnitten kodiert wird, wurde 1994 von dem Mathematiker Leonard M. Adleman (*1945) vorgeschlagen, einem der Schöpfer des RSA-Algorithmus (HBCI). Mithilfe eines »biochemischen DNA-Computers« löste er das Problem zumindest für sieben Städte.